import java.util.*;

/**
 * 690. 员工的重要性
 * https://leetcode-cn.com/problems/employee-importance/
 */
public class Solutions_690 {
    public static void main(String[] args) {
        List<Employee> list = new ArrayList<>();
        Employee obj1 = new Employee(1, 5, Arrays.asList(2, 3));
        Employee obj2 = new Employee(2, 3, Arrays.asList(4));
        Employee obj3 = new Employee(3, 4, new ArrayList<>());
        Employee obj4 = new Employee(4, 1, new ArrayList<>());

        list.add(obj1);
        list.add(obj2);
        list.add(obj3);
        list.add(obj4);

        int id = 1;  // output: 13
        int result = getImportance(list, id);
        System.out.println(result);
    }

    private static Map<Integer, Employee> map = new HashMap<>();
    private static int res = 0;

    /**
     * 需要查找到全部下属，通过递归实现
     */
    public static int getImportance(List<Employee> employees, int id) {
        // 遍历 employees，记录员工对象到 map 中，员工 id 为键
        for (Employee employee : employees) {
            map.put(employee.id, employee);
        }
        dfs(id);
        return res;
    }

    public static void dfs(int id) {
        Employee employee = map.get(id);
        res += employee.importance;
        for (int sub : employee.subordinates) {
            // 遍历员工 id 的直系员工
            dfs(sub);
        }
    }
}

class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;

    public Employee(int id, int importance, List<Integer> subordinates) {
        this.id = id;
        this.importance = importance;
        this.subordinates = subordinates;
    }
}